//动态规划
//1.定义状态            f(n):青蛙跳第n级台阶的总跳法数 
//2.定义状态转移方程     f(n)=f(n-1)+f(n-2);
//3.设置初始值          f(0)=1;f(1)=1;f(2)=2;
class Solution {
public:
    int numWays(int n) {
        if (n <= 1) 
            return 1;
        int dp[n + 1];
        dp[0] = 1;
        dp[1] = 1; 
        for (int i = 2; i < n + 1; ++i) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
};

